# lib.auk: Auk library
# Tim Menzies
# October 31, 2012

"""
Synopsis
========

    @include "lib.awk"

Description
===========

`lib.auk` holds some frequently used functions.
Highlights include:

+ `arg`:  named command-line flags

Conventions 
-----------

### Auk Lore ###

All code is formatted as _AukLore_; i.e. 

+ 52 characters wide max + Functions less than 60 lines.  
+ Indentations using two spaces per tab 
+ Comments in _discourse style_ that offers a running 
  commentary on the code.

Copyright
---------

Any code base must start with a copyright statement, which we can show
using `_lib`.

"""
function _lib(   o) {
  args("-who,(c) 2012 tim@menzies.us,"\
       "-what,lib.auk : useful common Auk functions",o)
  copyleft(o["-what"],o["-who"])
}
"""

`_lib` executes using the more general `copyleft` function that
accepts two strings describing `what` the code is and `who` has the
copyright.

"""
function copyleft(what,who) {
  prints(what,who," ",
    "This program is free software: you can ",
    "redistribute it and/or modify it under ",
    "the terms of the GNU Lesser General   ",
    "Public License as published by the Free ",
    "Software Foundation, either version 3 of ",
    "the License, or (at your option) any later",
    "version.",
    " ",
    "This program is distributed in the hope ",
    "that it will be useful, but WITHOUT ANY ",
    "WARRANTY; without even the implied warranty",
    "of MERCHANTABILITY or FITNESS FOR A",
    "PARTICULAR PURPOSE. See the GNU General ",
    "Public License for more details.",
    " ",
    "You should have received a copy of the GNU",
    "Lesser General Public License along with this",
    "program.  If not, see ",
    "<http://www.gnu.org/licenses/>.")
}
"""

List Stuff
==========

Initialize, Reset
-----------------

### a ###

Ensures that `x` is an empty array. The bad news is that, after call
this function, all information in `x` is gone. The good news is that,
after call this function, all information in `x` is gone.

"""
function a(x) { 
    split("",x,"") 
}
"""

### pairs ###

Build a list of key value pairs from the string of
`key1,value1,key2,value2,..`.

"""
function pairs(str,lst,   i,tmp,n) {
  split("",lst,"")
  n=split(str,tmp,",")
  for(i=1;i<n;i+=2)
    lst[tmp[i]]=tmp[i+1]
}
"""

### s2l ###

Build a list whose's key `i` equals `valueI`
from the string `value1,value2,value3`.

"""
function s2l(str,l,sep,   i,tmp,n) {
		split("",l,"")
		n=split(str,tmp,sep ? sep : ",")
		for(i=1;i<=n;i++)
				l[i]=tmp[i]
		return n
}
"""

### s2k ###

Build a _key_ list (where key=value) from the list
`key1,key2,key3,...`.

"""
function s2k(str,l,   i,tmp,n) {
  split("",l,"")
  n=split(str,tmp,",")
  for(i=1;i<=n;i++)
    l[tmp[i]]=tmp[i]
}
"""

Concatenation
-------------

Concat `x` and `y` to make `z`.

"""
function concat(x,y,z, i,n) {
    for(i in x) z[++n] = x[i]
    for(i in y) z[++n] = y[i]
 }
"""



Sets
----

### has ###

Return the position of `x` in the list `l` or 0 if
not found.

"""
function has(a,x,    i) {
  for(i in a)
    if (a[i] == x) return i
  return 0
}
"""

Get and Set Functions
---------------------

### push ###

Pushes a new value `x` onto the end of list
`a`. Returns `x`.

"""
function push(x,a) {
  return a[length(a)+1] = x
}

function push2(at,x,a) {
  a[at][length(a[at])+ 1] = x
}
"""

### any, anybut ###

`Any` returns any item (selected at random) from the
list `l`. Assumes that the indexes of `l` are
numberic.

"""
function any(l) {
  return l[int(rand()*length(l)) + 1]
}
"""

`Anybut` is similar to `any` but accepts two
optional arguments `but1` and `but2` that store
indexes _not_ to return.

"""
function anybut(l,but1,but2,          lives, x) {
  x = any(l)
  if (x==but1 || x==but2) 
    return lives > 9 ? x : anybut(l,but1,but2,lives+1)
  else 
    return x
}
""" 

The `anybut` function has limited patience in finding
things that are not `but1` or `but2`. After nine tries,
it gives up and returns whatever it found last.

### shuffle ###

Re-jig order.

"""
function shuffle(a,  i,j,n,tmp) {
  n=length(a)
  for(i=1;i<=n;i++) {
    j=i+round(rand()*(n-i));
    tmp=a[j];
    a[j]=a[i];
    a[i]=tmp;
  };
  return n;
}
"""

Sorting
-------

Gawk4 supports sorting for multi-dimensional
lists. The `xsort` function assumes that one key in
the list is _"x"_ and that we should sort on that
key.

"""
function xsort(r1,x1,r2,x2) {
    return x1["x"] - x2["x"]
}

function xsortDown(r1,x1,r2,x2) {
    return x2["x"] - x1["x"]
}

"""

GAWK4's `asort` function can sort these lists using a
programmer-specified function.  For example, `onum` and
`ostr` sort lists in numerical or string order.

"""
function onum(l,prefix) { o(l,prefix,"@ind_num_asc") }
function ostr(l,prefix) { o(l,prefix,"@ind_str_asc") }
"""

Printing
--------

### o ###

Auk's `o` function works recursively to print lists,
nested to any depth:

+ The optional `prefix` argument supplies a string that is printed
  with each argument. 

+  The actual sort order can be set by an optional
   `order` argument which, if not supplied, is
   determined by looking at the keys of the list.

"""
function o(l,prefix,order,   indent,   old,i) {
  if(!order)
    for(i in l) { 
      if (nump(i))
        order = "@ind_num_asc" 
      else 
        order = "@ind_str_asc"
      break
    }     
   old = PROCINFO["sorted_in"] 
   PROCINFO["sorted_in"]= order
   for(i in l) 
     if (isarray(l[i])) {
       print indent prefix "[" i "]"
       o(l[i],"",order, indent "|   ")
     } else
       print indent prefix "["i"] = (" l[i] ")"
   PROCINFO["sorted_in"]  = old 
}
"""

### l2s ###

Convert a list `l` to a string, with each item
seperated by `sep`. An optional `form` argument
(e.g. `"%5.3f"`) specifies the `printf` string for
numerics.

"""
function l2s(l,sep,form,   one,sep1,s,n,i) {
  form = form ? form : "%5.3f"
  s=""
  n=length(l)
  for(i=1;i<=n;i++)  {
    one = l[i]
    if (nump(one)) 
	    one = sprintf(form,one)
    s = s sep1 one
    sep1 = sep
  }
  return s 
}
"""

String Stuff
===========

### say ###

`Say` something to standard error.

"""
function say(x) {
    printf(x)>"/dev/stderr"
    fflush("/dev/stderr")
    return x
}
"""

### barph ###

`Barph` a string to standard error, return 0.

"""
function barph(x) {
  say("#E> " x "\n")
  return 0
}
"""

### stars ###

Generate a string of length `n` containing characters `s`.

"""
function stars(n,s,   out) {
  s = s ? s : "*"
  while (n-- > 0) out = out s
  return out
}

#####

function _2c(s) {
 gsub(_,",",s)
 return s
}

"""

Numerical Stuff
===============

Type Determination
------------------

### nump ###

Are you a number?

"""
function nump(x) { 
  return x=="" ? 0 : x == (0+strtonum(x)) 
}
"""

### abs ###

Absolute value of a number.

"""
function abs(x) { return x < 0 ? -1*x : x }
"""

### round ###

Round a number to the nearest integer.

"""
function round(x)      { 
  return int(x<0 ? x-0.5 : x+0.5) 
}
""" 

### p ###

Return a number rounded to a percent. Assumes a positive
number as input.

"""
function p (x) { return int(100*x + 0.5) }
"""

### mean ###      

Mean of a list.  

"""
function mean(a,    i,sum) {
  for(i in a) sum += a[i]
  return sum/length(a)
}
"""

### median ### 

"""
function median(a,   b,max) {
  max = asort(a,b)
  return b[int(max*0.5)]
}
function spread(a,   b,max) {
  max = asort(a,b)
  return b[int(max*0.75)] - b[int(max*0.25)]
}
"""

### l2sd ###

Find the standard deviation of a list.

"""
function l2sd(a,    i,n,x,delta,mean,m2) {
  for(i in a) {
    n    += 1
    x     = a[i]
    delta = x - mean
    mean += delta/n
    m2   += delta*(x -mean)
  }
  return sqrt(m2/(n-1))
}
"""

### normal ###

Sample a number from a `normal` distribution
with a certain `mean` and `standardDev`.

"""
function normal(mean, standardDev){  
  return mean + box_muller()*standardDev;
}
function box_muller(   w,n,x1,x2) {
  w=1;  
  while (w >= 1) { 
    x1= 2.0 * rand() - 1;  
    x2= 2.0 * rand() - 1; 
    w = x1*x1 + x2*x2
  };
  w = sqrt((-2.0 * log(w))/w);
  return x1 * w;
}
"""

### sd ###

Given `n` items that sum to `s` and whose sum of the
square of the items is `s2`, return the standard
deviation.

"""
function sd(n,s,s2,     m,tmp) {
  m = n - 1
  if (m <= 0) return 0
  else {
    tmp= (s2-((s*s)/n))/m
    if (tmp <= 0) 
      return 0
    else
      return sqrt(tmp)
}}
"""

Random Stuff
------------

### seed  ###

Sets the random number seed to either some passed
value or, if none, the number 1.  Useful for
controlling random number sequences; e.g. being able
to reproduce a set of steps controlled by a randoms
sequence.

"""
function seed(x) {
  x = x ? x : 1
  srand(x)
  say("Seed= " x "\n")
}
"""

Other Stuff
===========

Binary Search
-------------

A binary search function needs a primitive accessor
for a particular array cell.

"""
function binarySearchGet(a,x) { return a[x] }
"""

This is used by the general skeleton which,
at each step, discards half  the option space.

"""
function binarySearch(goal,a,at,  here,mid,lo,hi) {
  at = at ? at : "binarySearchGet"
  lo=1;hi=length(a)
  while(hi > lo) {
    mid  = int((lo + hi)/2)
    here = @at(a,mid)      
    if (here > goal)
	    hi = mid - 1
    else if (here < goal)
	    lo = mid + 1
    else break}
  return mid
}
"""

System
======

Command-line args
-----------------

### args ###

Returns non-zero if the command line arguments
satisfy the flags in `str`. If the command-line
flags are ok, then `opts` becomes a set of key=value
pairs where the `key` is one of the command-line
flags and `value` is the argument to those flags.
Note that if the argument is not given on the
command line, then `value` is taken from `str`.

The `str` takes the form:

    "-flag1,default1,-flag2,default2,--switch3,bool3"

Anything starting with `-` defined a flag that
expects an argument. Anything starting with `--`
defines a _switch_, i.e. a flag whose defaultvalue
is 0 or 1 and, if called on the command-line,
switches that value 1 to 0 or 0 to 1.

Here's a demo for the code:

"""
function _args(   opts) {
  args("-f,love,--open,1,-g,12,--h,0",opts)
  o(opts,"opts")
}
"""

Here's the main driver:

"""
function args(str,opts,    out) { 
  out = args1(str,ARGV,ARGC,opts)
  ARGC = length(ARGV)
  return out
}
function args1(str,a,n,opts,    i,j,x,val,tmp) {
  n = n ? n : length(a)
  pairs(str,opts)
  i=0
  while(1) {
    if (i>n) break
    i++
    x = a[i]
    if (x=="--") continue 
    if (x !~ /^-/)  break
    if (! (x in opts)) 
      return barph(x" : undefined flag")
    if (x ~ /^--/) {
       opts[x]= 1 - opts[x]
       continue
    }
    if (x ~ /^-/) {
      if (i >= n) 
        return barph(x" : missing arg")
      val = a[++i]
      opts[x] = nump(val) ? val + 0 : val 
    }}
  for(j=i+1;j<=n;j++)  # cache what's left 
    tmp[j-i]=a[j]
  split("",a,"")       # reset the input args
  for(j in tmp)        # copy cache to input args
    a[j] = a[j] 
  return 1
}
"""

### prints ###

A convenience function for printing many strings
(e.g. help text describing a function).


"""
function prints(a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,\
                b0,b1,b2,b3,b4,b5,b6,b7,b8,b9,\
                c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,\
                d0,d1,d2,d3,d4,d5,d6,d7,d8,d9,\
                e0,e1,e2,e3,e4,e5,e6,e7,e8,e9,\
                c,n,l,i) {
  c="______"
  n=s2l(\
  a0 c a1 c a2 c a3 c a4 c a5 c a6 c a7 c a8 c a9 c\
  b0 c b1 c b2 c b3 c b4 c b5 c b6 c b7 c b8 c b9 c\
  c0 c c1 c c2 c c3 c c4 c c5 c c6 c c7 c c8 c c9 c\
  d0 c d1 c d2 c d3 c d4 c d5 c d6 c d7 c d8 c d9 c\
  e0 c e1 c e2 c e3 c e4 c e5 c e6 c e7 c e8 c e9, \
  l,c)
  print ""
  for(i=1;i<=n;i++) {
    if (l[i] == "") 
      return 0
    print l[i] ~ /^ / ? "   " l[i] : l[i]
}}

function default(x,y) {
  return x==""? y : x
}
